package com.czk.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/23 20:45
 */
public class HoseChessBoard {
    /**
     * 棋盘的列数
     */
    private static int x;
    /**
     * 棋盘的行数
     */
    private static int y;
    /**
     * 标记棋盘的各个位置是否被访问过
     */
    private static boolean[] visited;
    /**
     * 使用一个属性标记棋盘所有位置是否被访问
     */
    private static boolean finished;

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        x=8;
        y=8;
        // 初始位置的行
        int row=1;
        // 初始列
        int column=1;
        int[][] chessBoard=new int[x][y];
        visited=new boolean[x*y];
        // 测试
        long start = System.currentTimeMillis();
        traversalChessboard(chessBoard,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println(end-start);
        // 遍历数组
        for (int[] ints : chessBoard) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 当前位置计算马儿还能访问那些位置
     * @param currentPoint 当前的位置
     * @return
     */
    public static List<Point> next(Point currentPoint){
        List<Point> ps=new ArrayList<>();
        // c创建一个point
        Point p1=new Point();
        // 一个马可以走的路径
        if ((p1.x=currentPoint.x-2)>=0&&(p1.y=currentPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x-1)>=0&&(p1.y=currentPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x+1)<x&&(p1.y=currentPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x+2)<x&&(p1.y=currentPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x+2)<x&&(p1.y=currentPoint.y+1)<y){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x+1)<x&&(p1.y=currentPoint.y+2)<y){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x-1)>=0&&(p1.y=currentPoint.y+2)<y){
            ps.add(new Point(p1));
        }
        if ((p1.x=currentPoint.x-2)>=0&&(p1.y=currentPoint.y+1)<y){
            ps.add(new Point(p1));
        }
        return ps;
    }

    /**
     *
     * @param chessBoard 棋盘
     * @param row 行
     * @param column 列
     * @param step 第几部
     */
    public static void traversalChessboard(int[][] chessBoard,int row,int column,int step){
        chessBoard[row][column]=step;
        // 标记该位置已访问
        visited[row*x+column]=true;
        // 获取当前位置可以走的位置集合
        List<Point> next = next(new Point(column, row));
        // 贪心算法优化，进行非递减排序
        sort(next);
        // 遍历集合
        while (!next.isEmpty()){
            // 取出一个可以走的位置
            Point remove = next.remove(0);
            // 判断该点已经被访问过
            if (!visited[remove.y*x+remove.x]){
                // 递归
                traversalChessboard(chessBoard,remove.y,remove.x,step+1);
            }
        }
        // 判断有没有完成任务
        // 回溯和运行的过程
        if (step<x*y&&!finished){
            chessBoard[row][column]=0;
            visited[row*x+column]=false;
        }else {
            finished=true;
        }
    }

    /**
     * 贪心算法优化减少回溯次数
     * @param list  点集合
     */
    public static void sort(List<Point> list){
        list.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 获取o1的下一步所有位置的个数
                List<Point> next = next(o1);
                int l1=next.size();
                List<Point> points=next(o2);
                int l2=points.size();
                if (l1<l2){
                    return -1;
                }else if (l1==l2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}
